import java.util.Scanner;

public class bisearch {
    public static void main(String[] args) {
        Scanner in= new Scanner(System.in);

        System.out.println("请输入待排序队列个数：");
        int n=in.nextInt();

        int[] p=new int[n];//调用进程数据结构，设置进程数量

        System.out.println("请依次输入队列的值：");

        for(int i=0;i<n;i++){
            p[i]=in.nextInt();
        }

        InsertSort(p);
        System.out.println("队列如下：");
        for (int i=0;i<n;i++){
            System.out.print(p[i]+"\t");
        }

        System.out.println();

        int k;
        System.out.println("请输入你想查找的数：");
        k=in.nextInt();

        if(Bisearch(p,k)==-1){
            System.out.println("抱歉，该数组不存在你要查找的数！");
        }
        else {
            System.out.println(k+"位于该数组的第"+Bisearch(p,k)+"位");
        }
    }

    public static int[] InsertSort(int[] p){
        int j;
        int m;
        for (int i=0;i<p.length;i++){
            j=i;
            while (j>0){
                if(p[j]<p[j-1]){
                    m=p[j];
                    p[j]=p[j-1];
                    p[j-1]=m;
                }
                j--;
            }
        }
        return p;
    }

    public static int Bisearch(int[] p,int k){
        int m=0;
        int l=p.length;
        int left=0;
        int right=p.length-1;
        while (left<=right){
            if(left>right){
                break;
            }
            m=(left+right)/2;
            if(k==p[m]){
                break;
            }
            else if(k<p[m]){
                right=m-1;
            }
            else if(k>p[m]){
                left=m+1;
            }
        }
        if(left>right){
            return -1;
        }
        else {
            return m+1;
        }
    }
}
